/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        124.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 9:33
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include <climits>
#include <algorithm>
#include "tree_node.h"
/*  二叉树中的最大路径和
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum */
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        if(root == nullptr)
            return 0;
        int value = INT_MIN;
        dfs(root,value);
        return value;
    }

private:
    int dfs(TreeNode *root,int &ans) {
        if (root == nullptr)
            return 0;
        int left =  dfs(root->left,ans);
        int right =  dfs(root->right,ans);
        int temp = root->val;
        temp +=(left + right);
        ans = std::max(temp,ans);
        return std::max(root->val + std::max(left, right), 0);
    }
};

